package 剑指offer;

public class _24反转链表 {
	/**
	 * 
	 *@time 2021年2月4日下午4:28:19
	 * 
	 *@param head
	 *@return ListNode
	 *
	 *@see迭代法
	 */
	  public ListNode reverseList1(ListNode head) {		
		  ListNode cur = head, pre = null;
	        while(cur != null) {
	            ListNode tmp = cur.next; // 暂存后继节点 cur.next
	            cur.next = pre;          // 修改 next 引用指向
	            pre = cur;               // pre 暂存 cur
	            cur = tmp;               // cur 访问下一节点
	        }
	        return pre;
		 
	   }
	  /**
	   * 
	   *@time 2021年2月4日下午4:28:54
	   * 
	   *@param head
	   *@return ListNode
	   *
	   *@see递归法
	   */
	  public ListNode reverseList2(ListNode head) {
		return digui(head, null);
		/**
		 * 第二种递归方法
		 *   if (head == null || head.next == null) {
            return head;
        	}
        	ListNode newHead = reverseList(head.next);
        	head.next.next = head;
        	head.next = null;
        	return newHead;
		 */
	  }
	  public ListNode digui(ListNode pre,ListNode cur) {
		if(cur==null)return pre;
		
		ListNode newListNode=digui(cur, cur.next);
		cur.next=pre;		
		return newListNode;	
	  }
	  
	  /**
	   * 
	   *@time 2021年2月4日下午4:32:41
	   * 
	   *@param head
	   *@return ListNode
	   *
	   *@see头插法（即迭代法）
	   *
	   */
      public ListNode reverseList3(ListNode head) {
		  if(head==null||head.next==null) return head;
		 
    	  ListNode newListNode=null;
    	  ListNode p =head;
    	  while (p!=null) {
			ListNode temp=p.next;//存储p.next
			//将p.next放newListNode就是使得后面的头插法
			p.next=newListNode;
			newListNode=p;
			//将存储的p.next放到p继续运行
			p=temp;
		}
    	  return newListNode;
	  }
}


 